This relates to packet communications and more particularly to improvements in the protocols associated with distributing the transmission resources among interconnected terminals.
A communications network is created physically by interconnecting terminals with communications channels. There are many such arrangements. To make these arrangements work, a protocol must be established to insure orderly communications. Many protocols are possible and, of course, some are better than others. It has long been recognized that standardization of protocols is beneficial to the industry and, in the United States, the IEEE 802.6 protocol is one such protocol. IEEE Standard. Distributed Wueue Dual Bus (DQDB) Metropolitan Area Network (MAN). 1988. Draft D.O, June 24, 1988.
The IEEE 802.6 Protocol is designed for transmission of packetized data in an arrangement not unlike the one depicted in FIG. 1. There, a plurality of terminals 10.1, 10.2, 10.3, . . . 10.N are interconnected via unidirectional buses 11 and 12. Bus 12 starts at terminal 10.1 and proceeds towards terminal 10.N in a "daisy chain" fashion, passing by the intermediate terminals. Bus 11 is similarly arranged, except that data flows from terminal 10.N towards 10.1. The information on buses 11 and 12 is arranged in time slots. Each time slot is designed to hold a packet of information in a data area. Each time slot also has a control area which includes a busy bit and a reservation bit. Each terminal, such as terminal 10.2, includes at least three elements: a source device 13, a transmitter-receiver module 14 and a transmitter-receiver module 15. Through module 14, source 13 of a terminal can couple packets onto bus 12 when it wishes to transmit information to a terminal on its right (i.e., down-stream) and when empty slots are available on the bus. Source 13 can, of course, be a "dumb" terminal, a computer, or a gateway to another network. When a terminal wishes to send a packet on bus 12, module 15 couples a reservation bit on bus 11. Placing a reservation bit on bus 11 causes all of the up-stream terminals (with reference to bus 12 and with respect to the terminal that sends the reservation bit) to make sure that each of them allows an empty data slot to pass unpopulated. This insures the existence of an empty slot on bus 12 and, therefore, the terminal that sent the reservation bit is able to load data into such an empty slot. The protocol is exactly the same when a terminal wishes to send packets to a terminal on its left, except that the roles of buses 11 and 12 and modules 14 and 15 are reversed.
For purposes of simplicity, the following discussion presumes only transmission of packets on bus 12, and the terms "down-stream" are with reference to bus 12.
In operation, a terminal i casts a packet of data onto bus 12 only when a free slot is available and enough reserved empty slots were allowed to pass without being populated so that terminals to the right of terminal i ("downstream" from terminal i), can populate the empty slots with awaiting packets. When information is inserted into an empty slot, the busy bit is set to 1. The fact that a packet awaits to be transmitted is communicated to up-stream terminals by a reservation bit that is coupled (i.e., set to 1) to the reservation bit position of a slot that passes by module 15 on bus 11 and which has an unset reservation bit.
More specifically, each transmitter-receiver module of a terminal contains a Request counter and a Count-down counter. When no data is to be transmitted by the terminal, the Count-down counter is not used. Reservation bits arriving at bus 11 increment the Request counter, and empty slots that pass unpopulated on bus 12 decrement the Request counter. In this manner, the value of the Request counter is indicative of the number of data slots that still must be passed unpopulated in order to satisfy the needs of down-stream terminals. When the terminal wishes to send a packet on bus 12, the contents of the Request counter are transferred to the Count-down counter, thereby capturing the value within the Request counter. The Request counter is reset at that time and the Count-down counter rather than the Request counter is decremented with every passing empty slot on bus 12. Reservation bit arriving at bus 11 continue to increment the Request counter. When the value in the Count-down counter reaches 0, the awaiting packet of the terminal is placed on the very next empty slot of bus 12. At that time, should there be another packet that is to be transmitted, the Request counter contents are again transferred to the Count-down counter and the process repeats. When no additional packets are to be transmitted, the operation reverts to the original mode, where the Request counter is decremented with each passing unpopulated slot on bus 12.
When terminals are separated by a considerable distance and each would like to transmit packets as quickly as possible, a problem can arise with protocol IEEE 802.6. To appreciate the potential problem it is helpful to keep in mind some typical system parameters. In a typical system, the transmission rate is 150.times.10.sup.6 bits per second, the speed of light in the medium is 2.4.times.10.sup.8 meters per second, and the slot size is 64 bytes (8 bits each). This translates to approximately 60 packets in transit on a 50 km link. Actually, more packets are in transit then this number because the coupling process in each terminal in the FIG. 1 arrangement introduces some delay (in modules 15 and 14). That means that for a 50 kilometer distance between terminals 10.1 and 10.N, the channel which comprises buses 11 and 12 may contain, perhaps, 126 packets in transit. This number is assumed in the discussion below, for sake of convenience.
A problem arises with the IEEE 802.6 protocol when two or more widely separated terminals desire to transmit large files (i.e., they wish to do a bulk transfer) and an up-stream terminal starts its transmission more than 63 time slots before the other. Such a terminal transmits on all time slots because no slots have been reserved by other terminals. Sometime later, when terminal 10.N-1 wishes to transmit information (e.g., to terminal 10.N), it finds all incoming slots busy. In accordance with protocol IEEE 802.6, it places a reservation bit on bus 11 for its first packet and waits for an empty slot to appear on bus 12. In the meantime, terminal 10.1 continues to populate empty slots until, 63 time slots later, it recognizes the reservation bit inserted by terminal 10.N-1 on bus 11 and allows one empty slot to pass on bus 12 unpopulated. It takes 63 additional time slots before that empty slot finally arrives at terminal 10.N-1. The result is that terminal 10.1 is able to transmit 125 packets for each packet transmitted by terminal 10.N-1.
This clear unfairness in the allocation of the available capacity (time slots) needs to be addressed.